1. Field of the Invention
The present invention generally relates to the non-deterministic determination of numbers and more specifically to the processing of a bit flow provided by a non-deterministic noise source (desired to be random).
The present invention, for example, applies to the non-deterministic generation of digital quantities intended to form ciphering or authentication keys used in cryptographic functions.
2. Discussion of the Related Art
The generation of a bit flow to form digital quantities in non-deterministic fashion uses a noise source capable of providing, directly or after conversion, a flow of binary states. The noise source may be digital or analog and exploit various disturbances (thermal noise, frequency variation, of an oscillator, etc.). The bit flow is generally exploited by words of fixed size (number of bits). The bit sequence distribution which characterizes the generator quality regarding the random character is evaluated by taking into account the desired word size.
It is frequently attempted to improve the random character of a bit flow by submitting it to processings downstream of the noise source. Such is the case, for example, for devices known as debiasers.
However, another problem regarding the generation of numbers, especially to form authentication or ciphering keys relates to the bit flow entropy, that is, the amount of useful information borne with respect to the number of transmitted bits. This phenomenon can be understood by considering a 64-bit word formed by the repeating of 8 identical bytes having equiprobable bit combinations. The useful information only comprises 8 bits, the other bits of the 64-bit word bearing no non-redundant information. The entropy then is one eighth with respect to a maximum entropy (1).
For example, a digital quantity generator to form a ciphering or authentication key over 1,024 bits cannot be considered as effectively providing keys over 1,024 bits if the representation of these keys is not optimal regarding entropy, that is, if some bits contain no useful information. The entropy is calculated according to the size of the words taken into account with respect to the possible repeating of sequences of lower sizes in the flow generated in non-deterministic fashion. Assuming that each byte in fact has a single entropy bit (entropy of one eighth), this amounts to stating that the key over 1,024 bits is equivalent to a key over 128 bits.
To qualify a random number generator, statistic entropy tests are conventionally performed by examining the results a posteriori to determine the number of information-bearing bits per word.
An example of such a test method is described in article “On the Security of Random Sources” by J-S. Coron published in 1999 in H. Imai and Y. Zheng (Eds.): PKC'99, LNCS 1560, pp. 29-42 (Springer Verlag).
A disadvantage of such statistic solutions is that they require significant and long calculations. In fact, the tests are performed on characterization of the non-deterministic generator, due to the number of required samples (several millions). It cannot be envisaged to integrate such mechanisms in the manufactured product, for example, for periodic evaluations throughout the product lifetime.